def apriori(D,minsup): #apriori算法
    '''
    :param D: 事务数据库
    :param minsup: (相对)支持度阈值
    :return:L：D中的频繁项集
    '''
    L=[] #[str,str,……,str]
    C=list(set([item for transcation in D for item in transcation]))
    while C:
        _L=frequent_gen(D,C,minsup)
        C=apriori_gen(_L)
        L.append(_L)
    return L
def frequent_gen(D,C,minsup): #根据候选项集Ck生成频繁k项集Lk
    '''
    :param D: 事务数据库
    :param C: k-候选项集
    :param minsup: (相对)支持度阈值
    :return: L: 频繁k项集
    '''
    L=[]
    static={i:0 for i in range(len(C))}
    for i,c in enumerate(C):
        size=len(c)
        for transcation in D:
            cnt=0
            for item in transcation:
                if item in c:
                    cnt+=1
            if cnt==size:
                static[i]+=1
    for i, c in enumerate(C):
        if static[i]/len(D)>=minsup:
            L.append(c)
    return L
def apriori_gen(L):  #根据频繁k-1项集L(k-1)生成候选集Ck
    '''
    :param L: 频繁k-1项集
    :return: C:候选k项集
    '''
    if not L:
        return []
    Length=len(L)
    size=len(L[0])
    C={}
    for i in range(Length-1):
        for j in range(i+1,Length):
            c=set(L[i]).union(set(L[j]))
            if len(c)==size+1:
                if not has_infrequent_subset(c,L):
                    c="".join(sorted(list(c)))
                    if c not in C:
                        C[c]=1
    return list(C.keys())
def has_infrequent_subset(c,L): #判断c的某个子项集是否是非频繁的
    '''
    :param c: 候选k项集
    :param L: 频繁k-1项集
    :return: 如果c存在非频繁子项集，返回True,否则返回False
    '''
    #判断c的所有k-1项子集是否都在L中
    c_=list(c)
    for i in range(len(c)):
        subset=set(c_[:i]+c_[i+1:])
        flag=False
        for l in L:
            if subset.issubset(set(l)): #某子集在L中，说明是频繁项集
                flag=True
                break
        if not flag:
            return True
    return False